Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 5
на тему:
" Розробка та дослідження ефективності методів пошуку даних"
з дисципліни:
"AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
Львів – 2013
Мета роботи.
Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.
1. Постановка задачі.
а) Анкетні дані (вміст файлу data.txt).
Pelenskiy,Vitaliy,Igorovuch,4,8,1994,Kyivstar,0,9,6,0,7,1,6,8,5,9,Lvivska,Komarno,Zelena,31,1,IKTA,EOM,KI-24,13,5,2013
б) Індивідуальне завдання.
Вибір варіанта індивідуального завдання:
Введемо позначення: DN = 4– день народження
MN = 8– місяць народження
RN = 1994 - рік народження
А1 = 80 – ASCII-код першої літери прізвища – велика латинська літера
А2 = 101 – ASCII-код другої літери прізвища – мала латинська літера
Вибір хеш-функції
№ варіанта = ( 4 + 1994 + 80 ) % 20 + 1 = 19
19. h(key) = [добуток АSCII-кодів перших трьох символів ключа (якщо ключ містить менше трьох символів, то відсутні символи вважати рівними першому символу) ] % m;
Розв'язання колізій при хешуванні
№ варіанта = ( 4 + 1994 + 101 ) % 25 + 1 = 25
25. методом відкритої адресації з функцією повторного хешування
hi(key) = ( h(key) + i ) % m
та шляхом зміни структури хеш-таблиці (кожну комірку хеш-таблиці замінити блоком з трьох комірок);
Організація хеш-таблиці №2
№ варіанта = ( 8 + 1994 + 80 ) % 11+ 1 = 4
4. методом закритого хешування;
2. Завдання 1. Організація хеш-таблиці №1.
2.1. Обчислення хеш-значень
(написати вигляд хеш-функції та стратегію розв'язання колізій; докладно показати приклади знаходження хеш-значень для перших 10 слів з вхідного файлаdata.txt).
Розв’язання колізії:
unsigned h(const string key, const size_t m) // обчислення хеш-значення у разі колізії
{
if (key.size() >= 3)
return (key[0]*key[1]*key[2]) % m;
if (key.size() == 2)
return (key[0]*key[1]*key[0]) % m;
if (key.size() == 1)
return (key[0]*key[0]*key[0]) % m;
}
unsigned hi(const string key, const unsigned m, const unsigned i)
{
return (h(key, m) + i) % m; // виклик функціїh(m) для хеш-значення
}
bool Add(Hash *hash, const string key) // обчислення хеш-значення
{
unsigned k = h(key, hash->m);
unsigned ki, i = 1;
if (hash->data[k][0] == "" || hash->data[k][0] == " ")
{
hash->data[k][0] = key;
return 1;
}
else if (hash->data[k][1] == "" || hash->data[k][1] == " ")
{
hash->data[k][1] = key;
return 1;
}
else if (hash->data[k][2] == "" || hash->data[k][2] == " ")
{
hash->data[k][2] = key;
return 1;
}
else
{
ki = hi(key, hash->m, i);
while (ki != k && hash->data[ki][0] != "" && hash->data[ki][0] != " " && hash->data[ki][1] != "" && hash->data[ki][1] != " " && hash->data[ki][2] != "" && hash->data[ki][2] != " ")
ki = hi(key, hash->m, ++i);
if (ki != k)
{
if (hash->data[ki][0] == "" || hash->data[ki][0] == " ")
{
hash->data[ki][0] = key;
return 1;
}
if (hash->data[ki][1] == "" || hash->data[ki][1] == " ")
{
hash->data[ki][1] = key;
return 1;
}
if (hash->data[ki][2] == "" || hash->data[ki][2] == " ")
{
hash->data[ki][2] = key;
return 1;
}
}
else
{
cout << "All memory used!" << endl;
return 0;
}
}
}
void Show(const Hash const *hash)
{
cout << "________________________________________________________________________________" << endl;
for (unsigned i = 0; i < hash->m; ++i)
cout << i+1 << "\t\t" << hash->data[i][0] << " " << hash->data[i][1] << " " << hash->data[i][2] << endl;
cout << "________________________________________________________________________________" << endl;
return;
}
bool Delete(Hash *hash, const string key)
{
...
